#include <vector>
#include <iostream>

using namespace std;

class Solution 
{
public:
    int trap(vector<int>& height) 
    {
        int left = 0;
        int right = height.size() - 1;
        int maxLeft = 0;
        int maxRight = 0;
        int totalWater = 0;

        while(left < right)
        {
            if(height[left] < height[right])
            {
                if(height[left] >= maxLeft)
                {
                    maxLeft = height[left];
                }
                else
                {
                    totalWater += maxLeft - height[left];
                }
                left++;
            }
            else
            {
                if(height[right] >= maxRight)
                {
                    maxRight = height[right];
                }
                else
                {
                    totalWater += maxRight - height[right];
                }
                right--;
            }
        }

        return totalWater;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& height) 
{
    cout << "[";
    for(int i = 0; i < height.size(); i++) 
    {
        cout << height[i];
        if(i < height.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() 
{
    Solution solution;
    
    // 测试案例1: [0,1,0,2,1,0,1,3,2,1,2,1]
    cout << "测试案例1:" << endl;
    vector<int> height1 = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    cout << "输入: ";
    printArray(height1);
    int result1 = solution.trap(height1);
    cout << "输出: " << result1 << endl;
    cout << "期望: 6" << endl << endl;
    
    // 测试案例2: [4,2,0,3,2,5]
    cout << "测试案例2:" << endl;
    vector<int> height2 = {4, 2, 0, 3, 2, 5};
    cout << "输入: ";
    printArray(height2);
    int result2 = solution.trap(height2);
    cout << "输出: " << result2 << endl;
    cout << "期望: 9" << endl << endl;
    
    // 测试案例3: 单个元素
    cout << "测试案例3 (单个元素):" << endl;
    vector<int> height3 = {3};
    cout << "输入: ";
    printArray(height3);
    int result3 = solution.trap(height3);
    cout << "输出: " << result3 << endl;
    cout << "期望: 0" << endl << endl;
    
    // 测试案例4: 两个元素
    cout << "测试案例4 (两个元素):" << endl;
    vector<int> height4 = {3, 1};
    cout << "输入: ";
    printArray(height4);
    int result4 = solution.trap(height4);
    cout << "输出: " << result4 << endl;
    cout << "期望: 0" << endl << endl;
    
    // 测试案例5: 递增序列
    cout << "测试案例5 (递增序列):" << endl;
    vector<int> height5 = {1, 2, 3, 4, 5};
    cout << "输入: ";
    printArray(height5);
    int result5 = solution.trap(height5);
    cout << "输出: " << result5 << endl;
    cout << "期望: 0" << endl << endl;
    
    // 测试案例6: 递减序列
    cout << "测试案例6 (递减序列):" << endl;
    vector<int> height6 = {5, 4, 3, 2, 1};
    cout << "输入: ";
    printArray(height6);
    int result6 = solution.trap(height6);
    cout << "输出: " << result6 << endl;
    cout << "期望: 0" << endl << endl;
    
    // 测试案例7: 山谷形状
    cout << "测试案例7 (山谷形状):" << endl;
    vector<int> height7 = {3, 0, 2, 0, 4};
    cout << "输入: ";
    printArray(height7);
    int result7 = solution.trap(height7);
    cout << "输出: " << result7 << endl;
    cout << "期望: 7 (3+1+3=7)" << endl << endl;
    
    // 测试案例8: 平坦地面
    cout << "测试案例8 (平坦地面):" << endl;
    vector<int> height8 = {0, 0, 0, 0};
    cout << "输入: ";
    printArray(height8);
    int result8 = solution.trap(height8);
    cout << "输出: " << result8 << endl;
    cout << "期望: 0" << endl << endl;
    
    // 测试案例9: 相同高度
    cout << "测试案例9 (相同高度):" << endl;
    vector<int> height9 = {2, 2, 2, 2};
    cout << "输入: ";
    printArray(height9);
    int result9 = solution.trap(height9);
    cout << "输出: " << result9 << endl;
    cout << "期望: 0" << endl << endl;
    
    // 测试案例10: 复杂情况
    cout << "测试案例10 (复杂情况):" << endl;
    vector<int> height10 = {5, 2, 1, 2, 1, 5};
    cout << "输入: ";
    printArray(height10);
    int result10 = solution.trap(height10);
    cout << "输出: " << result10 << endl;
    cout << "期望: 14 (3+4+3+4=14)" << endl << endl;
    
    // 测试案例11: 空数组
    cout << "测试案例11 (空数组):" << endl;
    vector<int> height11 = {};
    cout << "输入: ";
    printArray(height11);
    int result11 = solution.trap(height11);
    cout << "输出: " << result11 << endl;
    cout << "期望: 0" << endl << endl;
    
    return 0;
}